package com.husk.leetcode.dp;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/25
 */
public class Solution {

    /**
     * 120. 三角形最小路径和
     * <p>
     * https://leetcode-cn.com/problems/triangle/
     * <p>
     * f(i, j) = Math.min(f(i-1, j-1), f(i-1, j))+a[i][j]
     * f(0, 0) = a[0][0];
     * f(i, i) = f[i-1][i-1] + a[i][i];
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < n; i++) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        return Arrays.stream(f[n - 1]).min().getAsInt();
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * <p>
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
     * <p>
     * price[i]表示第i天股票价格
     * <p>
     * 这一天交易过后没有股票
     * dp[i][0] = max{dp[i-1][0], dp[i-1][1] + price[i]}
     * 前一天持有1只股票
     * dp[i][1] = max{dp[i-1][1], dp[i-1][0] - price[i]}
     * <p>
     * dp[0][0] = 0
     * dp[0][1] = -price[0]
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }

    /**
     * 714. 买卖股票的最佳时机含手续费
     * <p>
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
     * price[i]表示第i天股票价格
     * <p>
     * 这一天交易过后没有股票
     * dp[i][0] = max{dp[i-1][0], dp[i-1][1] + price[i] - fee}
     * 前一天持有1只股票
     * dp[i][1] = max{dp[i-1][1], dp[i-1][0] - price[i]}
     * <p>
     * dp[0][0] = 0
     * dp[0][1] = -price[0]
     *
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }


    /**
     * 300. 最长递增子序列
     * <p>
     * https://leetcode-cn.com/problems/longest-increasing-subsequence/
     * <p>
     * dp[i]标识以nums[i]结尾的最长递增子序列
     * dp[i] = max(dp[j]) + 1, 0<=j<i, nums[j] < nums[i]
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    /**
     * 198. 打家劫舍
     * <p>
     * 经典动态规划问题
     *
     * <p>
     * https://leetcode-cn.com/problems/house-robber/
     * <p>
     * dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
     * dp[0] = nums[0]
     * dp[1] = Math.max(nums[0], nums[1]);
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 213. 打家劫舍 II（房间围成一个圈）
     * <p>
     * https://leetcode-cn.com/problems/house-robber-ii/
     * <p>
     * 两个区间
     * 不偷窃最后一间房，[0, n-2]
     * 不偷窃第一间房,[1, n-1]
     * <p>
     * dp[start]=nums[start] //只有1间房
     * dp[start+1]=max(nums[start], nums[start+1]) // 只有两间房
     *
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] array1 = Arrays.copyOfRange(nums, 0, nums.length - 1);
        int[] array2 = Arrays.copyOfRange(nums, 1, nums.length);
        return Math.max(this.rob(array1), this.rob(array2));
    }

    @Test
    public void test() {
        int[] data = new int[]{1, 2, 3, 1};
        this.rob2(data);
    }


    /**
     * 70. 爬楼梯
     * <p>
     * https://leetcode-cn.com/problems/climbing-stairs/
     * <p>
     * dp[i] = dp[i-1]+dp[i-2]
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        // 解法1：动态规划
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 62. 不同路径
     * <p>
     * https://leetcode-cn.com/problems/unique-paths/
     * <p>
     * dp[i][j] = dp[i][j-1] + dp[i-1][j]
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 64. 最小路径和
     * <p>
     * https://leetcode-cn.com/problems/minimum-path-sum/
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }


    /**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     * <p>
     * https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        Queue<Character> queue = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (queue.contains(c)) {
                while (true) {
                    Character temp = queue.poll();
                    if (temp == c) {
                        break;
                    }
                }
            }
            queue.offer(c);
            if (queue.size() > max) {
                max = queue.size();
            }
        }
        return max;
    }

    /**
     * 1139. 最大的以 1 为边界的正方形 TODO
     * <p>
     * https://leetcode-cn.com/problems/largest-1-bordered-square/
     *
     * @param grid
     * @return
     */
    public int largest1BorderedSquare(int[][] grid) {

        return 0;
    }

    /**
     * 剑指 Offer 42. 连续子数组的最大和
     * https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
     * <p>
     * f(i)=Max(f(i-1)+nums[i], nums[i])
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    /**
     * 5. 最长回文子串
     * https://leetcode-cn.com/problems/longest-palindromic-substring/
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;

        // dp[][]表示s[i..j]是否是回文
        boolean[][] dp = new boolean[len][len];
        // 初始化所有长度为1的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int l = 2; l <= len; l++) {
            for (int i = 0, j = i + l - 1; j < len; i++, j++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 354. 俄罗斯套娃信封问题（二维最长上升子序列问题）
     * https://leetcode-cn.com/problems/russian-doll-envelopes/
     *
     * @param envelopes
     * @return
     */
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        Arrays.sort(envelopes, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            } else {
                return o2[1] - o1[1];
            }
        });
        // 最长上升子序列问题
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

}

